package leetcode.easy.q35;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class Q {
    public static void main(String[] args) {
        log.info("left insert:{}", new Solution().searchInsert(new int[]{1, 3, 4, 5}, 0));
        log.info("mid insert:{}", new Solution().searchInsert(new int[]{1, 3, 4, 5}, 2));
        log.info("right insert:{}", new Solution().searchInsert(new int[]{1, 3, 4, 5}, 7));
        log.info("found:{}", new Solution().searchInsert(new int[]{1, 3, 4, 5}, 3));
        log.info("left insert:{}", new Solution2().searchInsert(new int[]{1, 3, 4, 5}, 0));
        log.info("mid insert:{}", new Solution2().searchInsert(new int[]{1, 3, 4, 5}, 2));
        log.info("right insert:{}", new Solution2().searchInsert(new int[]{1, 3, 4, 5}, 7));
        log.info("found:{}", new Solution2().searchInsert(new int[]{1, 3, 4, 5}, 3));
    }
}

/**
 * 递归版本
 */
class Solution {
    public int searchInsert(int[] nums, int target) {
//        if (nums == null || nums.length == 0) return 0;
        return twoPartSearch(nums, 0, nums.length - 1, target);
    }

    private int twoPartSearch(int nums[], int left, int right, int target) {
        int mid = (left + right) / 2;
        if (mid == left || mid == right) {
            if (target <= nums[left]) return left;
            if (target <= nums[right]) return right;
            return right + 1;
        }
        if (target < nums[mid]) {
            return twoPartSearch(nums, left, mid, target);
        } else {
            return twoPartSearch(nums, mid, right, target);
        }
    }
}
/**
 * 循环版本
 */
class Solution2 {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid = (left + right) / 2;
        while (left != mid) {
            if (target > nums[mid]) {
                left = mid;
                mid = (left + right) / 2;
            } else if (target < nums[mid]) {
                right = mid;
                mid = (left + right) / 2;
            } else {
                return mid;
            }
        }
        return target <= nums[left] ? left : target <= nums[right] ? right : right + 1;
    }

}